package geekstudy.week10;

import java.util.*;

/**
 * 699. 掉落的方块
 * https://leetcode-cn.com/problems/falling-squares/
 *
 *
 * 执行结果：  通过  显示详情
 *
 * 添加备注
 * 执行用时：19 ms, 在所有 Java 提交中击败了76.64% 的用户
 * 内存消耗：39.8 MB, 在所有 Java 提交中击败了5.61% 的用户
 */
public class Week10FallingSquares {

    public List<Integer> fallingSquares(int[][] positions) {
        List<Integer> list = new ArrayList<Integer>();

        TreeSet<Integer> coordSet = new TreeSet<Integer>();
        for(int[] pos : positions) {
            coordSet.add(pos[0]);
            coordSet.add(pos[0] + pos[1] - 1);
        }
        Map<Integer, Integer> index = new HashMap<Integer, Integer>();
        int t = 0;
        for(int coord : coordSet) {
            index.put(coord, t++);
        }

        SegmentTree segmentTree = new SegmentTree(coordSet.size());
        int best = 0;
        for(int[] pos : positions) {
            int left = index.get(pos[0]);
            int right = index.get(pos[0] + pos[1] - 1);
            int high = segmentTree.query(left, right) + pos[1];
            segmentTree.update(left, right, high);
            best = Math.max(best, high);
            list.add(best);
        }

        return list;
    }




}

class SegmentTree {
    int n;
    int high;
    int[] tree;
    int[] lazy;

    SegmentTree(int n) {
        this.n = n;
        high = 1;
        for(;(1 << high) < n;) {
            high++;
        }
        tree = new int[2 * n];
        lazy = new int[n];
    }

    private void apply(int x, int val) {
        tree[x] = Math.max(tree[x], val);
        if(x < n) {
            lazy[x] = Math.max(lazy[x], val);
        }
    }

    private void pull(int x) {
        for(;x > 1;) {
            x >>= 1;
            tree[x] = Math.max(tree[x * 2], tree[x * 2 + 1]);
            tree[x] = Math.max(tree[x], lazy[x]);
        }
    }

    private void push(int x) {
        for(int size = high; size > 0; size--) {
            int y = x >> size;
            if(lazy[y] > 0) {
                apply(y * 2, lazy[y]);
                apply(y * 2 + 1, lazy[y]);
                lazy[y] = 0;
            }
        }
    }

    public void update(int left, int right, int high) {
        left += n;
        right += n;
        int l0 = left;
        int r0 = right;
        int ans = 0;
        for(; left <= right ;) {
            if( (left & 1) == 1) {
                apply(left++, high);
            }
            if( (right & 1) == 0) {
                apply(right--, high);
            }
            left >>= 1;
            right >>= 1;
            pull(l0);
            pull(r0);
        }
    }

    public int query(int left, int right) {
        left += n;
        right += n;
        int ans = 0;
        push(left);
        push(right);
        for(;left <= right;) {
            if( (left & 1) == 1 ) {
                ans = Math.max(ans, tree[left++]);
            }
            if( (right & 1) == 0 ) {
                ans = Math.max(ans, tree[right--]);
            }
            left >>= 1;
            right >>= 1;
        }
        return ans;
    }

}
